#include <stdio.h>
//
// Created by win10 on 24-12-25.
//
void printArray(int arr[],int size) {
    for(int i=0;i<size;i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}

//选择排序
void selectionSort(int arr[],int n){ //待排序的数组 数组的尺寸
    //定义几个临时变量
    int minIndex,temp;//最小值的小标 用于交换的临时变量
    //用外层的循环遍历数组里的每一个值
    for(int i=0;i<n-1;i++) {
        minIndex=i;//假设当前元素是最小值
        //内层的循环去寻找剩余部分的最小元素
        for(int j=i+1;j<n;j++) {
            if(arr[j]<arr[minIndex]){
                minIndex=j; //找到了更小的元素，更新最小元素的索引（下标）
            }
        }
        //若最小元素不是当前元素，则交换
        if(minIndex!=i) {
            temp=arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=temp;
        }
        printf("step %d: ",i+1);
        printArray(arr,n);
    }
    printf("sorted array: ");
    printArray(arr,n);
}
int main() {
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    selectionSort(arr,n);
}